package LeetcodeTest_twenty_nine;
//401. 二进制手表

import java.util.ArrayList;
import java.util.List;

public class readBinaryWatch
{
    public static void main(String[] args)
    {
        List<String> answer=new ArrayList<>();
        answer=Solution.readBinaryWatch(1);
        for(String value:answer)
            System.out.println(value);
    }
}
class Solution
{
    public static List<String> readBinaryWatch(int num)
    {
        ArrayList<String> result=new ArrayList<>();
        for (int i=0;i<=num;i++)
        {
            ArrayList<Integer> memory=new ArrayList<>();
            ArrayList<String> temp1=new ArrayList<>();
            ArrayList<String> temp2=new ArrayList<>();
            backtrace(i,0,4,memory,temp1);
            memory.clear();
            backtrace(num-i,0,6,memory,temp2);
            for(int j=0;j<temp1.size();j++)
            {
                for(int k=0;k<temp2.size();k++)
                {
                    result.add(temp1.get(j)+":"+temp2.get(k));
                }
            }
        }
        return result;
    }
    public static void backtrace(int length, int index, int n, ArrayList<Integer> memory,ArrayList<String> temp)
    {
        if(length>n)
            return;
        ArrayList<Integer> answer=new ArrayList<>(memory);
        if(answer.size()==length)
        {
            int sum=0;
            for(int i=0;i<length;i++)
            {
                sum+=answer.get(i);
            }
            if(n==4)
            {
                if(sum>11)
                    return;
                else
                    temp.add(Integer.toString(sum));
            }
            else
            {
                if(sum>59)
                    return;
                else if(sum<10)
                {
                    temp.add("0"+Integer.toString(sum));
                }
                else
                    temp.add(Integer.toString(sum));
            }
        }
        else
        {
            for(int i=index;i<n;i++)
            {
                answer.add((int) Math.pow(2,i));
                backtrace(length,i+1,n,answer,temp);
                answer.remove(answer.size()-1);
            }
        }
    }
}